Improved Genetic Algorithm for Multi-constrained 0-1 Knapsack Problem

doi:10.3969/j.issn.1006-2475.2012.09.035

Computer and Modernization ›› 2012, Vol. 1 ›› Issue (9): 140-142.doi: 10.3969/j.issn.1006-2475.2012.09.035

• 算法分析与设计 • Previous Articles Next Articles

Improved Genetic Algorithm for Multi-constrained 0-1 Knapsack Problem

LV Cong-ying1， HU Ping2， LIU Jiong2

1. College of Computer and Information Engineering, Nanyang Institute of Technology, Nanyang 473000, China;2. State Intellectual Property Office of the People’s Republic of China, Beijing 100088, China

Received:2012-05-04 Revised:1900-01-01 Online:2012-09-21 Published:2012-09-21

Abstract

Abstract: he improved strategies for GA are presented, and used to solve the MKP. These main improved strategies are: the solution of the LP-relaxed MKP is used as the initial solution; the repair and local improvement operators are used to avoid the loss of population diversity. By using a standard set of large-sized test data to test the new GA, the results show that the new GA has better performance and converges much faster to better solutions.


Key words: multi-constrained 0-1 knapsack problem, genetic algorithm, LP-relaxed algorithm, repair operator, local optimization

LV Cong-ying;HU Ping;LIU Jiong. Improved Genetic Algorithm for Multi-constrained 0-1 Knapsack Problem[J]. Computer and Modernization, 2012, 1(9): 140-142.

[1]	LIU Xian-zhuo, DENG Wei-si, XIE En-yan. Adaptive Protection System for Distribution Network Considering Grid Connection of Distributed Generation [J]. Computer and Modernization, 2023, 0(09): 120-126.
[2]	ZHANG Zhi-xia, XIE Bao-qiang. Natural Gas Load Forecasting Based on FCGA-LSTM and Transfer Learning [J]. Computer and Modernization, 2023, 0(07): 7-12.
[3]	WANG Min, XU Ying-hao, ZHU Xi-jun. Prediction Model of Diabetic Complications Based on BP Neural Network Optimized by Improved Genetic Algorithm#br# [J]. Computer and Modernization, 2022, 0(11): 69-74.
[4]	WANG Yang, CHEN Mei, LI Hui. FOCoR: A Course Recommendation Approach Based on Feature Selection Optimization [J]. Computer and Modernization, 2022, 0(10): 1-7.
[5]	RAN Hao-jie, WANG Hong-zhi. Distribution Center Site Selection of Fresh Agricultural Products Based on Improved Simulated Annealing Algorithm [J]. Computer and Modernization, 2022, 0(10): 36-40.
[6]	ZHAN Jun-wei, ZHUANG Yi. Mobile Edge Computing Task Offloading Model and Algorithm Based on Energy Consumption and Delay Optimization [J]. Computer and Modernization, 2022, 0(08): 86-93.
[7]	WU Dai-yang, ZHAO Jie, LIANG Jia-ming, DONG Zhen-ning, LIANG Zhou-yang. Host Matching for C2C Online Short-term Rentals [J]. Computer and Modernization, 2022, 0(06): 43-48.
[8]	XU Sheng-chao, XIONG Mao-hua. Optimization of Container Cloud Resource Allocation Based on Genetic Algorithm [J]. Computer and Modernization, 2022, 0(01): 108-112.
[9]	XU Ming, ZHANG Jian-ming, CHEN Song-hang, CHEN Hao. Multi-objective Optimization Algorithm for Flexible Job Shop Scheduling Problem [J]. Computer and Modernization, 2021, 0(12): 1-6.
[10]	ZHANG Lin-peng, WANG Xi-yuan, LI Qiang. Image Classification Based on Double-pooling Feature Weighted Convolutional Neural Network [J]. Computer and Modernization, 2021, 0(11): 67-71.
[11]	YANG Xiao-dong. Risk Assessment Model of Accounting Resource Sharing Management Based on Genetic Algorithm [J]. Computer and Modernization, 2021, 0(06): 24-28.
[12]	LIU Jun, PENG Hui-xian, HUANG Bin, Tony SHAY. Breast Cancer Diagnosis Model Based on BP-GamysBoost [J]. Computer and Modernization, 2021, 0(04): 8-14.
[13]	XU Sheng-chao. Using Genetic Algorithm for Virtual Machine Placement Optimization [J]. Computer and Modernization, 2020, 0(12): 25-31.
[14]	WU Hai-wei, WANG Xiao-zhong, ZHU Fa-shun, . A Scheduling Method of Smart Grid Based on Genetic Algorithm [J]. Computer and Modernization, 2020, 0(09): 122-126.
[15]	ZHANG Zhi-wei, GAN Gang. Service Vulnerability Mining of Android System Based on Genetic Algorithm [J]. Computer and Modernization, 2020, 0(08): 114-121.

Improved Genetic Algorithm for Multi-constrained 0-1 Knapsack Problem

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments